今天是Extra系列！

由於前面有用到Java的Integer.bitCount()，我們也說會來講解一下

那今天就來講吧！

大家可能會想：它是不是就一個迴圈，跑N個位元累計一下就好？

事實上呢……

請看！

這是什麼！？！？！？！？

這就是程式效率達到極致的……………天書啊！

好啦，那我們逐一的講解下去

（以下會用到前幾篇講到的東西，還沒看過建議先去看一下）

簡單來說bitCount()的原理是這樣

• 把原本二進位進行分組，把那組的數字變成表示原本小組中有幾個1
• 把有幾個1的數字合併相加

變為表示幾個1的舉例，假設四個一組：

• 1111 → 0100 [0100十進位是4，表示原本小組中有4個1]
• 0010 → 0001 [0001十進位是1，表示原本小組中有1個1]
• 0100 → 0001 [和上面一樣，1在哪個位置不影響]

接下來我們一行一行講解

i = i - ((i >>> 1) & 0x55555555);

這個步驟是兩兩分組，2個位元一組（參考上面的顏色）

• 左邊的i代表的是很多小組合起來的數字，這些分組代表原本數字某個區塊中有幾個1
• i >>> 1 → 向右移一位，代表原本是第二位的位元現在是第一位的位元
• (i >>> 1) & 0x55555555代表只留下第一位的位元

所以為什麼要這樣做？好像有點抽象？接下來看例子

如果偶數位是1，在十進位代表2，所以要減掉向右位移的自己（變成1）才能取到1（反正2-1才會變成1啦）
簡單來說，就是變成說明原本小組中有幾個1的東西

i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);

這一步驟就是各小組兩兩合併，變成4個位元一組
是相加而不是相減的原因是，這串數字已經是代表有幾個1的數字了，而不是原本的數字
(i >>> 2) & 0x33333333表示取出前面小組的數字，原理和上一步相同

有沒有覺得好像發現什麼規律了？

i = (i + (i >>> 4)) & 0x0f0f0f0f;

各小組兩兩合併成8個位元一組
& 0x0f0f0f0f 表示去掉前面小組的數字，因為你已經把前面小組加到後面小組了

i = i + (i >>> 8);

各小組兩兩合併成16個位元一組
大家可能會好奇，為什麼這裡沒有做Mask，後面會解釋（注意這步是兩個8位元一組的小組合併）

i = i + (i >>> 16);

最後兩組合併

return i & 0x3f;

0x3f → 00111111
32位元的數字最多就32個1，而32的二進位是00100000，所以這個1前面的必定是0
前面兩步驟不做Mask的原因是，在最後一次濾掉比較有效率（前面濾後面濾效果都一樣）
簡單來說就是 「前面的數字就隨便讓他加，反正最後都會刪掉」

整體步驟整理

• 把原本數字變成代表小組內有幾個1的數字，並兩兩分組
• 兩兩合併成4個位元一組，刪掉前面小組
• 兩兩合併成8個位元一組，刪掉前面小組
• 兩兩合併成16個位元一組
• 最後兩組合併
• 取有用的最後6個位元，return

還是很抽象怎麼辦？

個人建議再多思考一下，因為它本來就不是一下子就能想通的東西
過去曾經有實際講解過這個東西，那問題其實就在有沒有「想通」。它雖然是效率的極致，但了解背後原理就會發現，其實沒有想像中恐怖，反而還會覺得挺有趣的。